Batch 3 - Class 236 - Finding a tough mountain
(Zoom)
Pre-Class Exercise
- (Dudeney 242) A tube inspector has been appointed, and he has to inspect the 17 lines connecting 12 stations of the tube regularly. In each phase, he wants to cover as little distance as possible to inspect the entire system. Each link is 1 mile long. Provide the shortest route that enables him to do so - he is free to start and end at any station.
- Answer: 19 miles - BADGDEFIFCBEHKLIHGJK. Can also be thought of as BADEFCBEHKLIHGJK - this leaves DG and FI links which can be traversed twice whenever we are at any of these 4 stations.
Attendance Kabir, Vansh, Kushagra, Rhea, Rohan, Angad, Shikher, Aashvi, Anishka, Arnav, Arjun, Rehaan, SidharthM, Vivaan, Ayush, Aarkin
Class puzzles (powerpoint available)
We want to go mountain biking. When is mountain biking fun? When we go up and down - you don't want to keep going up or keep going down when you are mountain biking.
So lets take 6 points, number 1-6 representing the height of those points. We want to find a mountain, i.e. arrangement of these 6 points, so that we don't have a boring mountain. A boring mountain is one where there are four or more points going up or going down. Here is an example of a boring mountain:
.png)
Let students now guess sequences that they think work. Let other students comment on whether they work or not.
Once the 6 point problem is done, go to 7, 8 and so on. What is the largest mountain range you can go to?
- In order to get an intuition on largest range, let us first try with smaller sequences increasing/decreasing instead of 4.
- Solve for avoiding 1 increasing or decreasing, and see what is the largest mountain range
- Solve for avoiding 2 increasing or decreasing, and see what is the largest mountain range
- Solve for avoiding 3 increasing or decreasing, and see what is the largest mountain range
- Do you see a pattern? Can you guess what would be the largest mountain range to avoid an increasing/decreasing sequence of 4?
- Now let us see a more formal proof. We will label each number with a pair (x,y) where x is the length of longest ascending sequence till that number, and y is the length of longest descending sequence till that number
- Let students label each number
- Ask them to make observations. If they are unable to, ask them if any two numbers can have the same label. Why not?
- If two numbers n1 and n2 have the same label, n1 appearing before n2, then either n1>n2 in which case the descending number of n2 should be larger than n1, or n1<n2 in which case the ascending number of n2 should be larger than n1
- What does that mean in terms of maximum length of mountain, so that x and y are within 3?
- 9
- Hence any mountain more than 9 length must have a sequence that is at least 4 long!
- What is the minimum length of mountains that fails with 5 length sequence
- 16+1=17
- What would an easy way to get to an optimal solution? For example, in a mountain of length 16, how do you avoid 4 length sequence?
- Solve for length 9 and 3 sequence
- Divide the numbers into 3 blocks, ascend within each block and descend across blocks - 789456123 for example
- 16 length: 13 14 15 16 9 10 11 12 5 6 7 8 1 2 3 4
Lets go to a 3D mountain now. On a 4x4 grid, arrange 16 numbers, so that no row and no column has an ascending or descending sequence of 3 or more (maximum sequence length is 2)
.png)
- Answer:
.png)
Homework:
How to arrange ten soldiers in five lines in such a way that each line contains four soldiers exactly?
- Answer: Since five lines each contain four soldiers, that means 20 points of presence, and hence each soldier appears on two lines. Thus, if we draw any 5 non parallel lines, they will each intersect at a point leading to 5C2=10 points where the soldiers may be placed. Some answers below
.png)
.png)
.png)
References:
https://ia902701.us.archive.org/4/items/AmusementsInMathematicspdf/AmusementsInMathematics.pdf - Dudeney